package bintree.leetcode;

//105. 从前序与中序遍历序列构造二叉树

public class Num105_buildTreeByPreAndIn {
    private int index = 0;
    public TreeNode buildTree(int[] preorder, int[] inorder) {
        return buildTreeHelper(preorder,inorder,0,preorder.length-1);
    }

    private TreeNode buildTreeHelper(int[] preorder, int[] inorder, int left, int right) {
        if(left>right){
            return null;
        }
        if(index==preorder.length){
            return null;
        }

        TreeNode root = new TreeNode(preorder[index]);
        index++;
        int post = find(root.val,inorder);
        root.left = buildTreeHelper(preorder,inorder,left,post-1);
        root.right = buildTreeHelper(preorder,inorder,post+1,right);
        return root;
    }

    private int find(int val, int[] inorder) {
        for (int i = 0; i < inorder.length; i++) {
            if(inorder[i] == val){
                return i;
            }
        }
        return -1;
    }
}
